/**
请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点。传入函数的唯一参数为 要被删除的节点 。

现有一个链表 -- head = [4,5,1,9]，它可以表示为:

示例 1：

输入：head = [4,5,1,9], node = 5
输出：[4,1,9]
解释：给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
示例 2：

输入：head = [4,5,1,9], node = 1
输出：[4,5,9]
解释：给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.
*/

// 解题步骤
// 1， 将被删除节点的值改为下个节点
// 2， 删除下个节点

/**
 * @param {ListNode} node
 * @return {void} Do not return anything, modify node in-place instead.
 */
var deleteNode = function (node) {
  node.val = node.next.val
  node.next = node.next.next
};




/***
 * 定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
 */

// 解题思路
// 1，反转两个节点： 将n+1的next指向n
// 2, 反转多个节点： 双指针遍历链表，重复上述操作

// 解题步骤
// 1，双指针一前一后遍历链表
// 2. 反转指针

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function (head) {
  let p1 = head
  let p2 = null
  while (p1) {
    const tmp = p1.next
    p1.next = p2
    p2 = p1
    p1 = p1.next
  }
};

//LeetCode 2
/***
 * 给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807
 */

// 解题思路
// 模拟相加操作
// 需要遍历链表

// 解题步骤
// 新建一个空链表
// 遍历被相加的两个链表，模拟相加操作，将个位数追加到新链表上，将十位数留到下一位去相加


/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function (l1, l2) {
  const l3 = new ListNode(0) // 建一个空链表
  // 开始遍历链表 
  let p1 = l1
  let p2 = l2
  let p3 = l3


  let carry = 0 // 上一轮十位的值
  while (p1 || p2) { //p1 与 p2 指针只要有值 继续遍历链表
    const v1 = p1 ? p1.val : 0 // 对p1与p2长短不一的情况做处理，如果没对应的值就返回0
    const v2 = p2 ? p2.val : 0 // 对p1与p2长短不一的情况做处理，如果没对应的值就返回0
    const val = v1 + v2 + carry // 需要处理相加大于10的情况
    carry = Math.floor(val / 10)

    // 把个位上的数追加到新链表上
    p3.next = new ListNode(val % 10)

    if (p1) p1 = p1.next
    if (p2) p2 = p2.next
    p3 = p3.next // p3永远有值 不用做判断
  }
  if (carry) p3.next = new ListNode(carry)
  return l3.next
};

// leetcode 83
/**
 * 存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除所有重复的元素，使每个元素 只出现一次 。
   返回同样按升序排列的结果链表。
 * 输入：head = [1,1,2]
 * 输出：[1,2]
 */

// 解题思路
// 因为链表是有序的，所以重复元素一定是相邻的
// 遍历链表，如果发现当前元素和下个元素值相同，就删除下个元素值

// 解题步骤
// 1，遍历链表，如果发现当前元素和下个元素值相同，就删除下个元素值
// 2，遍历结束后，返回原链表的头部

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var deleteDuplicates = function (head) {
  let p = head
  while (p && p.next) { // 保证下个值也是有值的
    if (p.val === p.next.val) {
      p.next = p.next.next
    } else {
      p = p.next // 相同元素直接干掉
    }
  }
  return head
};

// 时间复杂度：O(n)
// 空间复杂度：O(1)


// LeetCode 141 
// 给定一个链表，判断链表中是否有环。

// 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

// 如果链表中存在环，则返回 true 。 否则，返回 false 。

// 输入：head = [3,2,0,-4], pos = 1
// 输出：true
// 解释：链表中有一个环，其尾部连接到第二个节点。

// 解题思路
// 1，两个人在圆形操场上的起点同时起跑，速度快的人一定会炒股欧速度慢的人一圈
// 2，用一快一慢两个指针遍历链表，如果指针能够相逢，那么链表就有圈

// 解题步骤
// 1，用一快一慢两个指针遍历链表，如果指针能够相逢，就返回 true
// 2, 遍历结束后，还没有相逢就返回 false

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function (head) {
  let p1 = head
  let p2 = head
  while (p1 && p2 && p2.next) {
    p1 = p1.next
    p2 = p2.next.next
    if (p1 === p2) {
      return true
    }
  }
  return false
};